package leetcode每日一题.leetcode20212;

import java.util.ArrayList;
import java.util.List;

/**
 * 1. 问题描述
 *      返回杨辉三角的第k行所有元素(所以从0开始，即第k行实际对应的是k+1层元素)
 *
 * 2. 算法分析
 *      1. 朴素的暴力法  找规律即可 时间复杂度为O(k^2)
 *          对于空间复杂度，我们可以使用List<List<Integer>> 来存每层的元素，每层的元素也放在List中
 *          最后返回上述定义的集合的最后一个List即可
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q012_杨辉三角2 {

    /**
     * 时间复杂度为O(k^2)  空间复杂度为O(k^2) 不推荐
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow1(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        if(rowIndex == 0) {
            res.add(1);
            return res;
        }
        if(rowIndex == 1) {
            res.add(1);
            res.add(1);
            return res;
        }
        List<List<Integer>> temp = new ArrayList<>();
        List<Integer> temp1 = new ArrayList<>(); temp1.add(1);
        List<Integer> temp2 = new ArrayList<>(); temp2.add(1); temp2.add(1);
        temp.add(temp1); temp.add(temp2);
        for(int i = 2; i <= rowIndex; i++) { // 层
            List<Integer> layer = new ArrayList<>();
            layer.add(1);
            for(int j = 1; j < i; j++) {
                layer.add(temp.get(i-1).get(j-1) + temp.get(i-1).get(j));
            }
            layer.add(1);
            temp.add(layer);
        }
        return temp.get(temp.size()-1);
    }

    /**
     * 优化上述代码，仅仅从代码层面进行优化  采用二维数组+动态规划
     * 空间复杂度为O(k^2 + k)  时间复杂度为O(k^2)
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow2(int rowIndex) {
        int[][] dp = new int[rowIndex+1][rowIndex+1];
        // 初始化
        dp[0][0] = 1;
        for(int i = 1; i <= rowIndex; i++) { // 层
            dp[i][0] = 1;
            dp[i][i] = 1;
        }
        // 动态规划过程
        for(int i = 2; i <= rowIndex; i++) { // 层
            for(int j = 1; j < i; j++) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
        // 扫描最后一行
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i <= rowIndex; i++) {
            res.add(dp[rowIndex][i]);
        }
        return res;
    }

    /**
     * 将空间复杂度优化到O(k)  使用滚动数组来优化，因为第i+1层只依赖于第i层的元素
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow3(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) { // 扫描层
            List<Integer> cur = new ArrayList<>(); // 滚动list
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(res.get(j-1)+res.get(j));
                }
            }
            res = cur;
        }
        return res;
    }
}
